A protocol for secure multi-party computation (MPC) allows a set of parties, each with a private input, to securely evaluate functionality (e.g., of a computational device) over party inputs. Generally, a secure MPC protocol should guarantee, (1) that the parties will not learn any information from the protocol other than the associated party output and what is inherently leaked from the output, (2) that the functionality was computed correctly, and (3) that all the inputs are independent. Performing secure computations over private data can enable organizations to mine data while preserving user privacy and make possible secure electronic voting.
However, many of the existing improvements in efficiency rely on new and more efficient instantiations of the cryptographic primitives and protocols underlying the generic MPC results. While the improvements in efficiency may be substantial, even the most efficient solutions cannot scale to handle the kind of massive datasets currently available. Indeed, at a certain scale, even plain non-secure algorithms become infeasible. Thus, the prospect of executing any MPC protocol is unreasonable.